package solution.dp;

import java.util.Stack;

import org.apache.commons.lang.StringUtils;
import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 */
public class Stairs {

	Stack<Integer> paths;
	int[] steps;

	void printPath(int n, int[] steps) {
		this.steps = steps;
		paths = new Stack<Integer>();
		printPathRec(n);
	}

	void printPathRec(int n) {
		if (n < 0)
			return;
		if (n == 0) {
			System.out.println(StringUtils.join(paths, ","));
			return;
		}
		for (int step : steps) {
			paths.push(step);
			printPathRec(n - step);
			paths.pop();
		}
	}

	@Test
	public void test() {
		printPath(10, new int[] { 1, 3, 5 });
	}

}
